#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next


class Solution:
    """
    @param: head: The first node of linked list.
    @param: n: An integer
    @return: Nth to last node of a singly linked list.
    1 --- 2 --- 3 --- 4 --- N, k = 2  (return 3)
    """
    def nthToLast(self, head, k):
        fast = head

        while fast and k:
            k -= 1
            fast = fast.next

        if k != 0:
            return None

        slow = head

        while fast:
            slow = slow.next
            fast = fast.next

        return slow


def main():
    print("start main")

    l4 = ListNode(4)
    l3 = ListNode(3, l4)
    l2 = ListNode(2, l3)
    l1 = ListNode(1, l2)

    s = Solution()
    ret = s.nthToLast(l4, 1)
    print(ret.val)
    print(ret)


if __name__ == "__main__":
    main()
